Preliminary results
All the problems are in minimization here, i.e. if an objective function \(z(x)\) is actually in maximisation, we will minimise \(-z(x)\) instead. Only binary variables are considered here.
1 Research questions
The first purpose of this study is to learn how some components of the branch and bound influences the behaviour of the algorithm it terms of computational time (expressed in seconds everywhere) and in term of number of nodes explored (i.e. how much nodes are developed in the branch and bound tree before the algorithm ends).
The branch and bound algorithm will always use the linear relaxation as lower bound set and the incumbent set as upper bound set. At each nodes, the extreme points of the lower bound set are checked for integrality and possibly added to the upper bound set. The components that will vary are:
the node selection : in the multi-objective branch and bound literature, depth first strategies are (almost) always used and are considered as better strategies than breadth first. However, our conjecture is that if a problem with an “easy” single-objective version is solved, then many non-dominated points may be found in a node close to the root node, in the early stages of the tree. Hence, using a breadth first strategy may provide a better upper bound set earlier in the algorithm, as a larger number of points are expected to be found shallow in the tree while only a few points can be found at each node deep in the tree (1 maximum at a leaf node for example). However, it is not clear to see what is the actual impact. Hence, here comes the first research question : how does depth and breadth first strategies affects the behaviour of the algorithm ? (computational time, number of nodes explored)
the variable selection : to the best of our knowledge, no extensive study for variable selection has been conducted in the literature. Sometimes, this component is even not mentioned. As it is not the main purpose of this study, only two rules that rely on the caracteristics of the lower bound set will be tested here.
mof : Most Often Fractional. The branching is operated on the variable that is the most often fractional among the extreme points of the lower bound set.
mfavg : Most Fractional in AVeraGe. The branching is operated on the variable such that its average value among the extreme points of the lower bound set is the most fractional, i.e. the closest to 0.5.
the branching scheme : in a regular branch and bound, branching is operated (i.e. sub-problems are created) in the decision space. In the bi-objective case, it has been shown that creating additional sub-problems in the objective space (procedure called objective branching in this study) leads to better computational times. A new research question arises here : what is the impact of objective branching on a branch and bound algorithm for solving problems with three objectives ? In order to address that, three versions of the branch and bound will be tested (with the best node and variable selection previously identified for each problem configuration):
None : no objective branching is performed. Hence, this version is just a regular branch and bound.
exact : objective branching is performed using the algorithm from [master thesis paper].
unique cone : a unique sub-problem is created at each node. In this case, objective branching is applied on the nadir point of the local upper bounds dominated by the lower bound set. See [master thesis paper] for more details.
The second purpose of this study is to learn how the caracteristics of an instance can affect its difficulty. The difficulty will be here mesured by the size of the non-dominated set, and the computational time required to solve the instance. The computational time will be determined using the branch and bound algorithm previously described. Note that the complexity of an objective space search algorithm is positively correlated to the size of the non-dominated set as the more non-dominated there are, the more integer programs have to be solved.
The focus will be here on the objective function coefficients. The first research question here is: does the range of the objective function coefficient has an impact on the difficulty of the problem ?. In order to answer that, three different ranges will be tested:
- \([1,10]\) : a small range of values.
- \([1,1000]\) : a large range of values
- \([1000,2000]\) : a large range of values, but shifted to larger values.
For the facility location problems, two sets of costs (i.e. coefficients of objective function) can be identified: the assignment costs (\(c_{ij}\)) and the facility opening costs (\(f_j\)). It is reasonable to assume that these two sets of costs may not take their values in the same range. Let the assignment costs take their values in \([a,b]\), the generation of the facility opening costs will be divided into two categories of instances:
- facility location easy : \(f_j \in [b+1,a+b]\). It is called “easy” because it seems that having high facility opening costs makes the problem easier (see later in the study).
- facility location hard : \(f_j \in [0.1a,0.1b]\). It is called “hard” because it seems that having small facility opening costs makes the problem harded (see later in the study).
The second research question related to that topic is: does the method used to generate the coefficients of the objective function has an impact on the difficulty of the problem ?. Indeed, the usual procedure to generate objective function is to generate the coefficients randomly in a given range \([a,b]\). However, one could imagine other way to generate coefficient. Four methods will be studied here.
- random : the coefficient are generated randomly with a uniform distribution in the range \([a,b]\). For three objectives, random generated coefficients looks as follows.
You must enable Javascript to view this page properly.
- sphere down : the coefficients are generated on the lower part of a sphere (see next picture). Note that the sphere is adjusted such that the coefficients are in the range \([a,b]\), i.e. the sphere is not necessarily included in \([a,b]^p\).
You must enable Javascript to view this page properly.
- sphere up : the coefficients are generated on the upper part of a sphere (see next picture). Note that the sphere is adjusted such that the coefficients are in the range \([a,b]\), i.e. the sphere is not necessarily included in \([a,b]^p\).
You must enable Javascript to view this page properly.
- 2box : the coefficients are generated randomly but in two specific parts of \([a,b]^p\) (see next picture).
You must enable Javascript to view this page properly.
2 Instances
List of test instances.
Several methods for generating the coefficient of the objective functions are tested here. This is given by the column coef.
- random : the coefficient are generated randomly in the inerval [a,b]
- spheredown : the coefficient are generated on the non-dominated part of a sphere in minimisation in the interval [a,b]
- sphereup : the coefficient are generated on the non-dominated part of a sphere in maximisation in the interval [a,b]
- 2box : the coefficients are generated randomly in two small boxes of R^3
3 Preliminary tests CPU time
Here are tested different combinations of variable and node selection for the basic branch and bound. In the following :
- depth = depth first strategy for node selection. The last node created is the first explored.
- breadth = breadth first strategy for node selection. The first node created is the first explored.
- mof = Most Often Fractional strategy for variable selection. Branching is operated on the variable that is the most often fractional among the extreme points of the lower bound set.
- mfavg = Most Fractional in AVeraGe strategy for variable selection Branching is operated on the variable that is the most fractional (i.e. the closest to 0.5) in average among the extreme points of the lower bound set.
3.1 Random coefficient generation
The coefficient are generated using the random method.
3.1.1 Range : [1,10]
The coefficient of the objective functions are in the range [1,10].
3.1.1.1 Knapsack
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.1.1.2 Assignment
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.1.1.3 Facility location easy
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.1.1.4 Facility location hard
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.1.2 Range : [1,1000]
The coefficient of the objective functions are in the range [1,1000].
3.1.2.1 Knapsack
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.1.2.2 Assignment
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.1.2.3 Facility location easy
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.1.2.4 Facility location hard
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.1.3 Range : [1000,2000]
The coefficient of the objective functions are in the range [1000,2000].
3.1.3.1 Knapsack
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.1.3.2 Assignment
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.1.3.3 Facility location easy
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.1.3.4 Facility location hard
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.2 Sphere Down coefficient generation
The coefficient are generated using the spheredown method.
3.2.1 Range : [1,10]
The coefficient of the objective functions are in the range [1,10].
3.2.1.1 Knapsack
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.2.1.2 Assignment
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.2.1.3 Facility location easy
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.2.1.4 Facility location hard
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.2.2 Range : [1,1000]
The coefficient of the objective functions are in the range [1,1000].
3.2.2.1 Knapsack
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.2.2.2 Assignment
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.2.2.3 Facility location easy
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.2.2.4 Facility location hard
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.2.3 Range : [1000,2000]
The coefficient of the objective functions are in the range [1000,2000].
3.2.3.1 Knapsack
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.2.3.2 Assignment
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.2.3.3 Facility location easy
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.2.3.4 Facility location hard
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.3 Sphere Up coefficient generation
The coefficient are generated using the sphereup method.
3.3.1 Range : [1,10]
The coefficient of the objective functions are in the range [1,10].
3.3.1.1 Knapsack
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.3.1.2 Assignment
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.3.1.3 Facility location easy
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.3.1.4 Facility location hard
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.3.2 Range : [1,1000]
The coefficient of the objective functions are in the range [1,1000].
3.3.2.1 Knapsack
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.3.2.2 Assignment
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.3.2.3 Facility location easy
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.3.2.4 Facility location hard
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.3.3 Range : [1000,2000]
The coefficient of the objective functions are in the range [1000,2000].
3.3.3.1 Knapsack
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.3.3.2 Assignment
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.3.3.3 Facility location easy
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.3.3.4 Facility location hard
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.4 Two boxes coefficient generation
The coefficient are generated using the random method.
3.4.1 Range : [1,10]
The coefficient of the objective functions are in the range [1,10].
3.4.1.1 Knapsack
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.4.1.2 Assignment
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.4.1.3 Facility location easy
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.4.1.4 Facility location hard
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.4.2 Range : [1,1000]
The coefficient of the objective functions are in the range [1,1000].
3.4.2.1 Knapsack
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.4.2.2 Assignment
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.4.2.3 Facility location easy
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.4.2.4 Facility location hard
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.4.3 Range : [1000,2000]
The coefficient of the objective functions are in the range [1000,2000].
3.4.3.1 Knapsack
Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.4.3.2 Assignment
Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.4.3.3 Facility location easy
Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
3.4.3.4 Facility location hard
Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.
4 Study on the coefficients of the objective function
In this section, relations between |YN| and various characteristics of the coefficient of the objective function are studied.
4.1 Knapsack
The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.
The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.
The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.
4.2 Assignment
The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.
The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.
The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.
4.3 Facility location easy
The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.
The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.
The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.
4.4 Facility location hard
The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.
The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.
The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.
end